{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Metaprogramming with Julia"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scare Quotes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Julia supports *metaprogramming*. This is similar to symbolic programming, where we deal with expressions (like $2+2$) as opposed to values (like $4$).\n",
    "\n",
    "Normally, Julia takes all code we give it as a set of instructions, and carries them out. If we type `2+2` it will faithfully add those numbers and give us the result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2+2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can prevent this from happening with quotation marks. Surrounding our code with `\"` treats it as a literal string of characters, without seeing it as code at all."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"2+2\""
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = \"2+2\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can then explicitly tell Julia to evaluate it later on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(Meta.parse(ans))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why go through this complicated way to add numbers? The trick is that when we have the expression `2+2`, we can modify it in various interesting ways. As a simple example, imagine replacing `+` with `-`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"2-2\""
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = replace(x, \"+\"=>\"-\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(Meta.parse(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We don't actually want to work with strings here; Julia has a much more powerful way to quote code, the frowny face operator `:()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(2 + 2)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = :(2+2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can quote larger expression, including blocks and entire function definitions. The keyword `quote` is an alternative to `begin` that returns the quoted block.\n",
    "\n",
    "In larger blocks, Julia will preserve line number information, which appears as a comment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quote\n",
       "    #= In[8]:2 =#\n",
       "    x = 2 + 2\n",
       "    #= In[8]:3 =#\n",
       "    hypot(x, 5)\n",
       "end"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quote\n",
    "  x = 2 + 2\n",
    "  hypot(x, 5)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(function mysum(xs)\n",
       "      #= In[9]:2 =#\n",
       "      sum = 0\n",
       "      #= In[9]:3 =#\n",
       "      for x = xs\n",
       "          #= In[9]:4 =#\n",
       "          sum += x\n",
       "      end\n",
       "  end)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    ":(function mysum(xs)\n",
    "    sum = 0\n",
    "    for x in xs\n",
    "      sum += x\n",
    "    end\n",
    "  end)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fruit of the Expression Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Strings support \"interpolation\", which allows us to easily build larger strings from smaller components."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "yields falsehood when preceded by its quotation\n"
     ]
    }
   ],
   "source": [
    "x = \"yields falsehood when preceded by its quotation\"\n",
    "println(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "'yields falsehood when preceded by its quotation' yields falsehood when preceded by its quotation\n"
     ]
    }
   ],
   "source": [
    "y = \"'$x' $x\"\n",
    "println(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(2 + 2)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = :(2+2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((2 + 2) * (2 + 2))"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    ":($x * $x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Root of all Eval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`eval` can do more than just returning a result. What happens if we quote something like a function definition?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(foo() = begin\n",
       "          #= In[15]:1 =#\n",
       "          println(\"I'm foo!\")\n",
       "      end)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(foo() = println(\"I'm foo!\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It doesn't actually do anything; yet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "ename": "UndefVarError",
     "evalue": "UndefVarError: foo not defined",
     "output_type": "error",
     "traceback": [
      "UndefVarError: foo not defined",
      "",
      "Stacktrace:",
      " [1] top-level scope at In[16]:1"
     ]
    }
   ],
   "source": [
    "foo()  # throws UndefVarError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But evaluating `ex` brings `foo` to life!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "foo (generic function with 1 method)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(ex)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I'm foo!\n"
     ]
    }
   ],
   "source": [
    "foo()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using interpolation, we can construct a function definition on-the-fly; in fact, we can make a whole series of functions at once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "foo() = begin\n",
      "        #= In[19]:2 =#\n",
      "        println(\"I'm foo!\")\n",
      "    end\n",
      "bar() = begin\n",
      "        #= In[19]:2 =#\n",
      "        println(\"I'm bar!\")\n",
      "    end\n",
      "baz() = begin\n",
      "        #= In[19]:2 =#\n",
      "        println(\"I'm baz!\")\n",
      "    end\n"
     ]
    }
   ],
   "source": [
    "for name in [:foo, :bar, :baz]\n",
    "  println(:($name() = println($(\"I'm $(name)!\"))))\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And then bring them to life with `eval`, too."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "for name in [:foo, :bar, :baz]\n",
    "  eval(:($name() = println($(\"I'm $(name)!\"))))\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I'm bar!\n"
     ]
    }
   ],
   "source": [
    "bar()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I'm baz!\n"
     ]
    }
   ],
   "source": [
    "baz()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This can be an *extremely* useful trick when wrapping APIs (say, from a C library or over HTTP). APIs often define a list of available functions, so you can grab that and generate the whole wrapper at once! See Clang.jl, TensorFlow.jl, or the Base linear algebra wrappers for examples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Original sin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a more practical example. Consider the following definition of the `sin` function, based on the Taylor series.\n",
    "\n",
    "$$sin(x) = \\sum_{k=1}^{\\infty} \\frac{(-1)^k}{(1+2k)!} x^{1+2k}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mysin (generic function with 1 method)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mysin(x) = sum((-1)^k/factorial(1+2k) * x^(1+2k) for k = 0:5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.4794255386041834, 0.479425538604203)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mysin(0.5), sin(0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To see where we are right now, we'll benchmark it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "BenchmarkTools.Trial: \n",
       "  memory estimate:  112 bytes\n",
       "  allocs estimate:  6\n",
       "  --------------\n",
       "  minimum time:     443.791 ns (0.00% GC)\n",
       "  median time:      490.977 ns (0.00% GC)\n",
       "  mean time:        571.891 ns (5.38% GC)\n",
       "  maximum time:     211.678 μs (99.70% GC)\n",
       "  --------------\n",
       "  samples:          10000\n",
       "  evals/sample:     196"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using BenchmarkTools\n",
    "@benchmark mysin(0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Right now, this is much slower than it could be. The reason is that we're looping over `k`, which is relatively expensive. It'd be much faster to write out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mysin (generic function with 1 method)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mysin(x) = x - x^3/6 + x^5/120 # + ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But this is tedious to write, and no longer looks like the original Taylor series. It's harder to tell if we've made a mistake, and we easily modify it. Is there a way to get the best of both worlds?\n",
    "\n",
    "How about getting Julia to write out that code for us?\n",
    "\n",
    "To start with, let's consider a symbolic version of the `+` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "plus (generic function with 1 method)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plus(a, b) = :($a + $b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(1 + 2)"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plus(1, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With `plus` we can do more interesting things, like symbolic `sum`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(+, 1:10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(((((((((1 + 2) + 3) + 4) + 5) + 6) + 7) + 8) + 9) + 10)"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(plus, 1:10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given that, we can also sum over symbolic variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((x ^ 2 + x) + 1)"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(plus, [:(x^2), :x, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This gives us an important piece of the puzzle, but we also need to figure out _what_ we're summing. Let's crate a symbolic version of the Taylor series above, which interpolates the value of `k`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((1 * x ^ 5) / 120)"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k = 2\n",
    ":($((-1)^k) * x^$(1+2k) / $(factorial(1+2k)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we have one term, we can generate as many as we like."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6-element Array{Expr,1}:\n",
       " :((1 * x ^ 1) / 1)         \n",
       " :((-1 * x ^ 3) / 6)        \n",
       " :((1 * x ^ 5) / 120)       \n",
       " :((-1 * x ^ 7) / 5040)     \n",
       " :((1 * x ^ 9) / 362880)    \n",
       " :((-1 * x ^ 11) / 39916800)"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "terms = [:($((-1)^k) * x^$(1+2k) / $(factorial(1+2k))) for k = 0:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And sum them –"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":((((((1 * x ^ 1) / 1 + (-1 * x ^ 3) / 6) + (1 * x ^ 5) / 120) + (-1 * x ^ 7) / 5040) + (1 * x ^ 9) / 362880) + (-1 * x ^ 11) / 39916800)"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(plus, ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And create a function definition out of it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(mysin(x) = begin\n",
       "          #= In[36]:1 =#\n",
       "          (((((1 * x ^ 1) / 1 + (-1 * x ^ 3) / 6) + (1 * x ^ 5) / 120) + (-1 * x ^ 7) / 5040) + (1 * x ^ 9) / 362880) + (-1 * x ^ 11) / 39916800\n",
       "      end)"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    ":(mysin(x) = $ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mysin (generic function with 1 method)"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.4794255386041834, 0.479425538604203)"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mysin(0.5), sin(0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "BenchmarkTools.Trial: \n",
       "  memory estimate:  0 bytes\n",
       "  allocs estimate:  0\n",
       "  --------------\n",
       "  minimum time:     28.162 ns (0.00% GC)\n",
       "  median time:      31.374 ns (0.00% GC)\n",
       "  mean time:        32.995 ns (0.00% GC)\n",
       "  maximum time:     117.487 ns (0.00% GC)\n",
       "  --------------\n",
       "  samples:          10000\n",
       "  evals/sample:     991"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@benchmark mysin(0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On my machine `sin2` takes about 50 *nano*seconds to run – not bad for a naive implementation. If we challenged a photon to a twenty metre sprint, we'd win!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Beneath the Expression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's really just a normal tree data structure, and we can take a look inside it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ex.head = :call\n",
      "ex.args = Any[:f, :x, :y]\n"
     ]
    }
   ],
   "source": [
    "ex = :(f(x, y))\n",
    "ex = Expr(:call, :f, :x, :y)\n",
    "@show ex.head;\n",
    "@show ex.args;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In our example above, we replace `+` with `-` in a string. In an expression, we can do that by altering the `.args` of the expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(2 + 2)"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(2+2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(2 - 2)"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.args[1] = :-\n",
    "ex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(ex)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that larger, more complex expressions are a bit trickier than this. They are *nested*, which means that the expression `2+3` is contained inside the larger expression `1 + (2 + 3)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(1 + (2 + 3))"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(1 + (2 + 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Array{Any,1}:\n",
       "  :+      \n",
       " 1        \n",
       "  :(2 + 3)"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex.args"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A package called MacroTools provides a way to deal with this. It shows us *all* sub-expressions in turn, allowing us to decide how we want to change them. It can be thought of as a bit like a find-and-replace operation. Here's an example that finds all integers in an expression, and increments them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import Pkg; Pkg.add(\"MacroTools\")\n",
    "using MacroTools\n",
    "using MacroTools: postwalk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(2 + (3 + 4))"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "postwalk(ex) do x\n",
    "  x isa Integer ? x+1 : x\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get a feel for what's happening, you can use `@show` to see what `postwalk` sees.\n",
    "\n",
    "(`@show` is Julia's single most useful feature; if you don't understand what code is doing, throw it in and see what's happening.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = 1\n",
      "x = 2\n",
      "x = 3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "3-element Array{Int64,1}:\n",
       " 1\n",
       " 2\n",
       " 3"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "map(x -> @show(x), [1,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = :+\n",
      "x = 1\n",
      "x = :+\n",
      "x = 2\n",
      "x = 3\n",
      "x = :(2 + 3)\n",
      "x = :(1 + (2 + 3))\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       ":(1 + (2 + 3))"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "postwalk(ex) do x\n",
    "  @show x\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MacroTools also provides tools for *pattern matching* over expressions. `a_ + b_` acts as a template; if the expression provided look like the template, `a` and `b` will match the two things be added. If not, they'll just be `nothing`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(2 + 3)\n",
    "@capture(ex, a_ + b_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 3)"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a, b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(f(2,3))\n",
    "@capture(ex, a_ + b_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(nothing, nothing)"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a, b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can finally use this to replace _all_ `+`s with `-`s in an expression, rather than just one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(3 * x ^ 2 + (2x + 1))"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = :(3x^2 + (2x + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(3 * x ^ 2 - (2x - 1))"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "postwalk(ex) do x\n",
    "  @capture(x, a_ + b_) || return x\n",
    "  :($a - $b)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Macro Agressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You have probably seen macros already – basic features in Julia like `@show`, `@time` and `@inline` are really macros. For basic usage, it's enough to think of them as simple annotations that alter how code is run. But we now know enough to dig into how they work under the hood.\n",
    "\n",
    "Normal functions never see _code_, only _values_. If we pass `2+2` to a function, it sees `4`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "foo (generic function with 2 methods)"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function foo(x)\n",
    "  @show x\n",
    "  return x\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = 4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "foo(2+2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Macros are much like function, but they see _code_ that was passed to them, like the expressions that we saw above. Macros get a chance to manipulate this code and alter how it behaves."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "@foo (macro with 1 method)"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "macro foo(x)\n",
    "  @show x\n",
    "  return x\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = :(2 + 2)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@foo(2+2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a simple example, we can replace one of the arguments to `+` and get a different result back."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "@foo (macro with 1 method)"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "macro foo(x)\n",
    "  x.args[2] = 5\n",
    "  return x\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@foo(2+2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MacroTools provides a useful tool, `@expand`, to see what's going on inside a macro; it reveals the code that the macro returns without running it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       ":(5 + 2)"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@expand @foo(2+2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can of course use this on the macros that come with Julia, and it's a good way to learn how they work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0.000001 seconds (4 allocations: 160 bytes)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@time 2+2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quote\n",
       "    #= util.jl:154 =#\n",
       "    local crab = (Base.gc_num)()\n",
       "    #= util.jl:155 =#\n",
       "    local chicken = (Base.time_ns)()\n",
       "    #= util.jl:156 =#\n",
       "    local okapi = 2 + 2\n",
       "    #= util.jl:157 =#\n",
       "    chicken = (Base.time_ns)() - chicken\n",
       "    #= util.jl:158 =#\n",
       "    local dogfish = (Base.GC_Diff)((Base.gc_num)(), crab)\n",
       "    #= util.jl:159 =#\n",
       "    (Base.time_print)(chicken, dogfish.allocd, dogfish.total_time, (Base.gc_alloc_count)(dogfish))\n",
       "    #= util.jl:161 =#\n",
       "    (Base.println)()\n",
       "    #= util.jl:162 =#\n",
       "    okapi\n",
       "end"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@expand @time 2+2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's do something more advanced. Using the techniques we developed above, we can find-and-replace `+` expressions in code. We'll still do the addition, but we'll also log what we added for debugging purposes.\n",
    "\n",
    "First, let's make an example expression using quotation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quote\n",
       "    #= In[65]:2 =#\n",
       "    s = 0\n",
       "    #= In[65]:3 =#\n",
       "    for x = xs\n",
       "        #= In[65]:4 =#\n",
       "        s = s + x\n",
       "    end\n",
       "    #= In[65]:6 =#\n",
       "    return s\n",
       "end"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = quote\n",
    "  s = 0\n",
    "  for x in xs\n",
    "    s = s + x\n",
    "  end\n",
    "  return s\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use `ex` to develop the code transformation we want, and check that the code does the right thing.}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quote\n",
       "    #= In[65]:2 =#\n",
       "    s = 0\n",
       "    #= In[65]:3 =#\n",
       "    for x = xs\n",
       "        #= In[65]:4 =#\n",
       "        s = begin\n",
       "                #= In[66]:4 =#\n",
       "                println(\"Adding \" * string(s) * \" to \" * string(x))\n",
       "                #= In[66]:5 =#\n",
       "                s + x\n",
       "            end\n",
       "    end\n",
       "    #= In[65]:6 =#\n",
       "    return s\n",
       "end"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "postwalk(ex) do x\n",
    "  @capture(x, a_ + b_) || return x\n",
    "  quote\n",
    "    println(\"Adding \" * string($a) * \" to \" * string($b))\n",
    "    $x\n",
    "  end\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we just wrap this in a macro, and we can add it to a normal function definition!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "@log_adds (macro with 1 method)"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "macro log_adds(ex)\n",
    "  postwalk(ex) do x\n",
    "    @capture(x, a_ + b_) || return x\n",
    "    quote\n",
    "      println(\"Adding \" * string($a) * \" to \" * string($b))\n",
    "      $x\n",
    "    end\n",
    "  end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mysum (generic function with 1 method)"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@log_adds function mysum(xs)\n",
    "  sum = 0\n",
    "  for x in xs\n",
    "    sum = sum + x\n",
    "  end\n",
    "  return sum\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Adding 0 to 1\n",
      "Adding 1 to 2\n",
      "Adding 3 to 3\n",
      "Adding 6 to 4\n",
      "Adding 10 to 5\n",
      "Adding 15 to 6\n",
      "Adding 21 to 7\n",
      "Adding 28 to 8\n",
      "Adding 36 to 9\n",
      "Adding 45 to 10\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mysum(1:10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Adding and removing `@log_adds` is much nicer than inserting the debug calls by hand, especially if you have lots of `+`s in the code. Perhaps you can extend the macro to support logging other operators, like `-`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generated Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Generated functions_ are a new metaprogramming tool unique to Julia. This section will briefly describe and motivate them, and [this blog post](http://mikeinnes.github.io/2017/08/24/cudanative.html) gives more examples for the interested reader.\n",
    "\n",
    "Essentially, a generated function is like a macro that operates on _types_ rather than expression trees. If we try to inspect arguments, we'll see their types rather than their values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "gadd (generic function with 1 method)"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@generated function gadd(a, b)\n",
    "  Core.println(\"a = $a, b = $b\")\n",
    "  :(a+b)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a = Int64, b = Float64\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "7.5"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gadd(5, 2.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Generated functions become more powerful when working with more complex types. For example, notice how arrays store their rank inside the type, so this is something we can generate code for."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2×2 Array{Float64,2}:\n",
       " 0.618286  0.431531\n",
       " 0.58246   0.555899"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rand(2,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Array{Float64,2}"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "typeof(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why might this be useful? If you write code to deal with arrays, you'll notice that you often need a `for` loop for each dimension of the array. If you want to work with a 7D array, you need to write seven nested loops!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mysum (generic function with 3 methods)"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function mysum(xs::Array{<:Any,1})\n",
    "  sum = 0\n",
    "  for i = 1:length(xs)\n",
    "    sum += xs[i]\n",
    "  end\n",
    "  return sum\n",
    "end\n",
    "\n",
    "function mysum(xs::Array{<:Any,2})\n",
    "  sum = 0\n",
    "  for i = 1:size(xs,1)\n",
    "    for j = 1:size(xs, 2)\n",
    "      sum += xs[i]\n",
    "    end\n",
    "  end\n",
    "  return sum\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Where other languages simply hard-code a version of each function for vectors, matrices and perhaps 3D arrays, Julia allows us to easily write N-dimensional algorithms by generating nested loops as needed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "kernelspec": {
   "display_name": "Julia 1.0.5",
   "language": "julia",
   "name": "julia-1.0"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.0.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
